package 数据结构和算法.剑指offer.树.树的子结构;

import 工具.动态生成二叉树.DynamicTreeUtil;
import 工具.打印.PrintUtil;
import 数据结构和算法.数据结构.普通二叉树.TreeNode;

/**
 * 树的子结构
 * <p>
 * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值
 * <p>
 * 通常二叉树的题型使用递归技巧
 */
public class Test {
    public static void main(String[] args) {
        int[] arrayParent = {3, 1, 4, 2, 5};
        int[] arrayChild = {4, 2, 5};
        TreeNode A = DynamicTreeUtil.createDynamicTree(arrayParent);
        TreeNode B = DynamicTreeUtil.createDynamicTree(arrayChild);
        PrintUtil.println(isSubStructure(A, B));
    }

    public static boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && recur(A, B) || recur(A.getLeftTreeNode(), B) || recur(A.getRightTreeNode(), B);
    }

    public static boolean recur(TreeNode A, TreeNode B) {
        if (null == B) {
            return true;
        }

        if (A == null || A.getValue() != B.getValue()) {
            return false;
        }

        return recur(A.getLeftTreeNode(), B.getLeftTreeNode()) && recur(A.getRightTreeNode(), B.getRightTreeNode());
    }
}
